package Hot100.Medium.BinaryTree;

import Hot100.Easy.LC104.TreeNode;

public class LC235_lowestCommonAncestorOfBST {
    public static void main(String[] args) {

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 根据二叉搜索树的特性，根节点左子树的值肯定比根节点小，右子树值都比根节点大
        // 因此如果要找的节点与root差值相乘大于0，则继续向下寻找，因为在同一边
        // 如果小于0，证明该root就是最近公共祖先，等于0，root就是pq其中一个，因此直接返回root
        while((long)(root.val - p.val) * (root.val - q.val) > 0){
            // 只用p与root比较来确定方向，因为进入while循环就意味着p、q在同一边
            root = p.val < root.val? root.left : root.right;
        }
        return root;
    }

    // 如果不想强转解决乘法溢出
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            // 避免乘法溢出
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }

}
